package com.algorithm.middleware.LFU;


import java.util.HashMap;
import java.util.LinkedList;

/**
 * @author liyanhao
 * @Date 2023-02-12 20:33
 * LFU  Least Frequently Used
 * 最不经常使用LFU算法要求应支持以下两种操作
 * get(key) 如果键存在于缓存中 则获取键的值，否则返回-1
 * put(key,value) 如果键不存在，则设置或插入值，当缓存达到容量是，则应该在插入新项之前，
 * 使最近不经常使用的项无效，
 * 可以再O(1)时间内完成以上操作
 * 1 O(1)时间完成 使用HashMap
 * 2 这个算法要求缓存达到容量时 可以删除最近不经常使用的项 那么对于每一组(k,v)对象，
 * 都需要维护一个fred属性，记录使用的次数
 * 3 算法即要求在O(1)找到fred的最小项目，考虑使用一个hashMap 他的key的次数，
 * Value是(k,v)对象，每个操作一个kv对时，就将其升入一个次数对应的value中
 * 4 算法要求使用次数相等是，要删除最近最少使用的键，
 * 因此可以在相同频率的key中维护一个双向链表
 * 最近使用的对象放在对象的头部，删除时直接删除在尾部。
 */
public class LFU {
    private int capacity;//容量
    private int minFred;//最小次数
    private HashMap<Integer, Node> cache;
    //次数对应的Node节点链表多个
    private HashMap<Integer, LinkedList<Node>> fredMap;

    public LFU(int capacity) {
        this.capacity = capacity;
        cache = new HashMap<>(capacity);
        fredMap = new HashMap<>();
        minFred = 0;
        this.capacity = capacity;
    }

    public int get(int key) {
        if (capacity == 0) {
            return -1;
        }
        Node node = cache.get(key);
        if (node == null) {
            return -1;
        }
        fredIncrease(node);
        return node.getValue();
    }

    //维护次数
    private void fredIncrease(Node node) {
        int fred = node.getFred();
        LinkedList<Node> fredList = fredMap.get(fred);
        fredList.remove(node);
        if (node.getFred() == minFred && fredList.isEmpty()) {
            minFred++;
        }
        fredList = fredMap.get(fred + 1);
        if (fredList == null || fredList.size() == 0) {
            fredList = new LinkedList<>();
            fredMap.put(fred + 1, fredList);
        }
        fredList.addFirst(node);
        node.fredInc();
    }

    public void put(int key, int value) {
        if (capacity == 0) {
            return;
        }
        Node node = cache.get(key);
        if (node != null) {
            node.setValue(value);
            fredIncrease(node);
            return;
        }
        node = new Node(key, value);
        if (cache.size() == capacity) {
            LinkedList<Node> fredList = fredMap.get(minFred);
            Node last = fredList.removeLast();
            cache.remove(last.getKey(),last);
        }
        cache.put(key, node);
        LinkedList<Node> fredList = fredMap.get(0);
        if (fredList == null) {
            fredList = new LinkedList<>();
            fredMap.put(0, fredList);
        }
        fredList.addFirst(node);
        minFred = 0;
    }

    public static void main(String[] args) {
        LFU cache = new LFU(3);
        cache.put(3,1);
        cache.put(2, 1);
        System.out.println(cache.cache.keySet());
        cache.put(2, 2);
        System.out.println(cache.cache.keySet());
        cache.put(4, 4);
        System.out.println(cache.cache.keySet());
        cache.put(5, 5);
        System.out.println(cache.cache.keySet());
    }

}



























